Real-time, multi-user distributed applications, such as online multi-player games or distributed interactive simulations (DIS), are becoming increasingly popular due to advances in game design and the availability of broadband Internet access to the end-user. Online multi-player games can be implemented either using the peer-to-peer model or the client-server model. In the peer-to-peer model players send their actions to each other and react on the received action, whereas in the client-server model all messages from players that carry their actions are ordered at a single server. In the peer-to-peer model, event consistency has been well studied using the concepts of logical clocks, causal ordering and total ordering in distributed systems. In the client-server model, consistency is automatically guaranteed because messages from all the players are only delivered at the central game server and, therefore, all messages follow both causal and total ordering. However, fairness in neither model has been addressed. Today most online multi-player games are implemented based on a client server model. This is due to the complexity of a peer-to-peer model based implementation as well as security restrictions that prevent peer-to-peer communication. The present invention focuses on games based on the client-server model. The design and implementation of such games should include an underlying fairness property for the players. This is challenging, however, in cases where players, distributed over wide geographic areas, participate in a game together.
In the client-server model, an authoritative game server is set up and all players or clients contact this game server to play the game against one another. The game server keeps track of the global state of the game. Players send their actions to the game server in messages referred to as action messages. The game server then processes the actions in sequence, changes the global state, and notifies players of the effects of their actions in messages termed state update messages or simply update messages. The state change that is communicated to the players may lead to more action messages being sent to the game server. The only communication in the system is between the game server and players. Players themselves do not send messages to one another, neither do they play any active role in deciding the ordering of actions in the game. Because of the real-time nature of online multi-player games, the majority of action and state update messages are sent over UDP; only a few messages are sent over TCP and only at game start-up. Because of this, applications have built-in mechanisms to handle message loss. For example, messages contain absolute location of objects instead of relative ones, therefore, there is no dependency on previous messages in case they are lost.
Much of the focus on improving real-time, online multi-player games is on how to reduce player experienced response time. For timely state updates at player consoles, dead reckoning is commonly used to compensate for packet delay and loss. For client-server based first person shooter games, Y. W. Bernier, “Latency Compensation Methods in Client/Server In-game Protocol Design and Optimization,” in Proc. of Game Developers Conference '01, 2001, discuses a number of latency compensating methods at the application level which are proprietary to each game. These methods are aimed at making large delays and message loss tolerable for players but do not consider the problems introduced by varying delays from the server to different players.
Using the current best-effort Internet, players can experience erratic game progress that often prevents a player from responding effectively or appropriately. This can lead to player frustration, especially if the gaming environment is competitive. In addition, because the game server is in charge of updating global states, and the network delay from the game server to different players is different, players may receive the same state update at different times. Furthermore, players' action messages can also take different times to reach the game server, therefore unfairness in processing player action messages can be created at the game server. A player further away from the game server or connected to the server through congested or slower links will suffer from longer message delay. Because of this, even fast reacting players may not be given credit for their actions, leading to an unfair advantage for players with small message delays.